A sliding window protocol is a feature of packet-based data transmission protocols. Sliding window protocols are used where reliable in-order delivery of packets is required, such as in the Data Link Layer (OSI model) as well as in the Transmission Control Protocol (TCP).
Conceptually, each portion of the transmission (packets in most data link layers, but bytes in TCP) is assigned a unique consecutive sequence number, and the receiver uses the numbers to place received packets in the correct order, discarding duplicate packets and identifying missing ones. The problem with this is that there is no limit of the size of the sequence numbers that can be required.
By placing limits on the number of packets that can be transmitted or received at any given time, a sliding window protocol allows an unlimited number of packets to be communicated using fixed-size sequence numbers.
For the highest possible throughput, it is important that the transmitter is not forced to stop sending by the sliding window protocol earlier than one round-trip delay time (RTT). The limit on the amount of data that it can send before stopping to wait for an acknowledgment should be larger than the bandwidth-delay product of the communications link. If it is not, the protocol will limit the effective bandwidth of the link.
Contents |
In any communication protocol based on automatic repeat request for error control, the receiver must acknowledge received packets. If the transmitter does not receive an acknowledgment within a reasonable time, it re-sends the data.
A transmitter that does not hear an acknowledgment cannot know if the receiver actually received the packet; it may be that the packet was lost in transmission (or damaged; if error detection finds an error, the packet is ignored), or it may be that an acknowledgment was sent, but it was lost. In the latter case, the receiver must acknowledge the retransmission, but must otherwise ignore it.
Likewise, the receiver is usually uncertain about whether its acknowledgments are being received.
The transmitter and receiver each have a current sequence number nt and nr, respectively. They each also have a window size wt and wr. The window sizes may vary, but in simpler implementations they are fixed. The window size must be greater than zero for any progress to be made.
As typically implemented, nt is the next packet to be transmitted, i.e. the sequence number of the first packet not yet transmitted. Likewise, nr is the first packet not yet received. Both numbers are monotonically increasing with time; they only ever increase.
The receiver may also keep track of the highest sequence number not yet received; the variable ns is one more than the sequence number of the highest sequence number received. For simple receivers that only accept packets in order (wr=1), this is the same as nr, but can be greater if wr>1. Note the distinction: all packets below nr have been received, no packets above ns have been received, and between nr and ns, some packets have been received.
When the receiver receives a packet, it updates its variables appropriately and transmits an acknowledgment with the new nr. The transmitter keeps track of the highest acknowledgment it has received na. The transmitter knows that all packets up to, but not including na have been received, but is uncertain about packets between na and ns; i.e. na ≤ nr ≤ ns.
The sequence numbers always obey the rule that na ≤ nr ≤ ns ≤ nt ≤ na + wt. That is:
Whenever the transmitter has data to send, it may transmit up to wt packets ahead of the latest acknowledgment na. That is, it may transmit packet number nt as long as nt < na+wt.
In the absence of a communication error, the transmitter soon receives an acknowledgment for all the packets it has sent, leaving na equal to nt. If this does not happen after a reasonable delay, the transmitter must retransmit the packets between na and nt.
Techniques for defining "reasonable delay" can be extremely elaborate, but they only affect efficiency; the basic reliability of the sliding window protocol does not depend on the details.
Every time a packet numbered x is received, the receiver checks to see if it falls in the receive window, nr ≤ x < ns+wr. (The simplest receivers only have to keep track of one value nr=ns.) If it falls within the window, the receiver accepts it. If it is numbered nr, the receive sequence number is increased by 1, and possibly more if further consecutive packets were previously received and stored. If x > nr, the packet is stored until all preceding packets have been received.[1] If x≥ns, the latter is updated to ns=x+1.
If the packet's number is not within the receive window, the receiver discards it and does not modify nr or ns.
Whether the packet was accepted or not, the receiver transmits an acknowledgment containing the current nr. (The acknowledgment may also include information about additional packets received between nr or ns, but that only helps efficiency.)
Note that there is no point having the receive window wr larger than the transmit window wt, because there is no need to worry about receiving a packet that will never be transmitted; the useful range is 1 ≤ wr ≤ wt.
So far, the protocol has been described as if sequence numbers are of unlimited size, ever-increasing. However, rather than transmitting the full sequence number x in messages, it is possible to transmit only x mod N, for some finite N. (N is usually a power of 2.)
For example, the transmitter will only receive acknowledgments in the range na to nt, inclusive. Since it guarantees that nt−na ≤ wt, there are at most wt+1 possible sequence numbers that could arrive at any given time. Thus, the transmitter can unambiguously decode the sequence number as long as N > wt.
A stronger constraint is imposed by the receiver. The operation of the protocol depends on the receiver being able to reliably distinguish new packets (which should be accepted and processed) from retransmissions of old packets (which should be discarded, and the last acknowledgment retransmitted). This can be done given knowledge of the transmitter's window size. After receiving a packet numbered x, the receiver knows that x < na+wt, so na > x−wt. Thus, packets numbered x−wt will never again be retransmitted.
The lowest sequence number we will ever receive in future is ns−wt
The receiver also knows that the transmitter's na cannot be higher than the highest acknowledgment ever sent, which is nr. So the highest sequence number we could possibly see is nr+wt ≤ ns+wt.
Thus, there are 2wt different sequence numbers that the receiver can receive at any one time. It might therefore seem that we must have N ≥ 2wt. However, the actual limit is lower.
The additional insight is that the receiver does not need to distinguish between sequence numbers that are too low (less than nr) or that are too high (greater than or equal to ns+wr). In either case, the receiver ignores the packet except to retransmit an acknowledgment. Thus, it is only necessary that N ≥ wt+wr. As it is common to have wr<wt (e.g. see Go-Back-N below), this can permit larger wt within a fixed N.
Although commonly distinguished from the sliding-window protocol, the stop-and-wait ARQ protocol is actually the simplest possible implementation of it. The transmit window is 1 packet, and the receive window is 1 packet. Thus, N=1+1=2 possible sequence numbers (conveniently represented by a single bit) are required.
The transmitter alternately sends packets marked "odd" and "even". The acknowledgments likewise say "odd" and "even". Suppose that the transmitter, having sent an odd packet, did not wait for an odd acknowledgment, and instead immediately sent the following even packet. It might then receive an acknowledgment saying "expecting an odd packet next". This would leave the transmitter in a quandary: has the receiver received both of the packets, or neither?
Go-Back-N ARQ is the sliding window protocol with wt>1, but a fixed wr=1. The receiver refuses to accept any packet but the next one in sequence. If a packet is lost in transit, following packets are ignored until the missing packet is retransmitted, a minimum loss of one round trip time. For this reason, it is inefficient on links that suffer frequent packet loss.
Suppose that we are using a 3-bit sequence number, such as is typical for HDLC. This gives N=2³=8. Since wr=1, we must limit wt≤7. This is because, after transmitting 7 packets, there are 8 possible results: Anywhere from 0 to 7 packets could have been received successfully. This is 8 possibilities, and the transmitter needs enough information in the acknowledgment to distinguish them all.
If the transmitter sent 8 packets without waiting for acknowledgment, it could find itself in a quandary similar to the stop-and-wait case: does the acknowledgment mean that all 8 packets were received successfully, or none of them?
The most general case of the sliding window protocol is Selective Repeat ARQ. This requires a much more capable receiver, which can accept packets with sequence numbers higher than the current nr and store them until the gap is filled in.
The advantage, however, is that it is not necessary to discard following correct data for one round-trip time before the transmitter can be informed that a retransmission is required. This is therefore preferred for links with low reliability and/or a high bandwidth-delay product.
The window size wr need only be larger than the number of consecutive lost packets that can be tolerated. Thus, small values are popular; wr=2 is common.
The extremely popular HDLC protocol uses a 3-bit sequence number, and has optional provision for selective repeat. However, if selective repeat is to be used, the requirement that nt+nr ≤ 8 must be maintained; if wr is increased to 2, wt must be decreased to 6.
Suppose that wr =2, but an unmodified transmitter is used with wt =7, as is typically used with the go-back-N variant of HDLC. Further suppose that the receiver begins with nr =ns =0.
Now suppose that the receiver sees the following series of packets (all modulo 8):
Because wr =2, the receiver will accept and store the final packet 0 (thinking it is packet 8 in the series), while requesting a retransmission of packet 7. However, it is also possible that the transmitter failed to receive any acknowledgments and has retransmitted packet 0. In this latter case, the receiver would accept the wrong packet as packet 8. . The solution is for the transmitter to limit wt ≤6. With this restriction, the receiver knows, after receiving packet 6, that the transmitter's na ≥1, and thus the following packet numbered 0 must be packet 8. If all acknowledgements were lost, then the transmitter would have to stop after packet 5.
There are many ways that the protocol can be extended:
The protocol can be extended to support packet reordering, as long as the distance can be bounded; the sequence number modulus N must be expanded by the maximum misordering distance.